1711E - XOR Triangle - CodeForces Solution

MOD = 998244353
TRANS = [6, 3, 7, 4, 1, 0]

s = input().strip()
dp = [0] * 7 + [1]
for c in map(int, s):
    dp1 = [0] * 8
    for i in range(8):
        for k in TRANS:
            if c:
                dp1[k & i] += dp[i]
            elif (k & i) == 0:
                dp1[i] += dp[i]
    dp = [x % MOD for x in dp1]
n = int(s, base=2) + 1
print((n**3 + 3 * n**2 - n - 3 * sum(dp)) % MOD)